//	ID : pallab81
// 	PROG : 562
// 	LANG : C++
// 	2011-07-15-16.38.58 Friday
//
// 	"I have not failed, I have just found 10000 ways that won't work.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>

#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>

using namespace std;

#define fo(i,ed) for(int i = 0 ; i < ed ; ++i )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define f first
#define s second


int n_coin;
int weight[ 150 ];
int rem[ 150 ][ 50900 ];
int sum;

inline void read() {
    sum=0;
    scanf("%d",&n_coin);
    fo(i,n_coin) {
        scanf("%d",&weight[i]);
        sum+=weight[i];
    }
}
inline int recur(int index, int now_sum) {
    int &best = rem[ index ] [ now_sum ];
    if(index==n_coin) {
        best = abs( now_sum - sum );
        return best;
    }

    if( best!=-1 )return best;
    int na_niye = recur( index+1, now_sum);
    int niye = recur( index+1, now_sum+weight[index] );
    best = min(na_niye, niye);
    return best;
}
inline void proc() {
    memset( rem, -1, sizeof(rem) );
    recur(0,0);

    int retval,i;
    for(i=sum/2; i>=0; --i ) {
        if( rem[n_coin][i]!=-1 ) {
            int a = sum-i;
            int b = i;
            retval = abs(a-b);
            break;
        }

    }

    printf("%d\n", retval);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt","rt",stdin);
#endif
    int cases;
    scanf("%d",&cases);
    for(; cases; --cases) {
        read();
        proc();
    }

    return 0;
}


